package arithmetic;

import java.util.Random;

/**
 * 动态规划的几个例子
 */
public class Dynamic {
	int maxsequence3(int a[], int len)  
	{  
	    int maxsum, maxhere;  
	    maxsum = maxhere = a[0];   //初始化最大和为a【0】  
	    for (int i=1; i<len; i++) {  
	        if (maxhere <= 0)  
	            maxhere = a[i];  //如果前面位置最大连续子序列和小于等于0，则以当前位置i结尾的最大连续子序列和为a[i]  
	        else  
	            maxhere += a[i]; //如果前面位置最大连续子序列和大于0，则以当前位置i结尾的最大连续子序列和为它们两者之和  
	        System.out.println("**"+maxhere);
	        if (maxhere > maxsum) {  
	            maxsum = maxhere;  //更新最大连续子序列和  
	        }  
	    }  
	    return maxsum;  
	}  
	
	public static void main(String[] args) {
		int[] d = new int[10000];
		for (int i=0;i<d.length;i++) {
			Random random = new Random();
			d[i] = random.nextInt(11);
			if (d[i] >= 6) {
				if (d[i] == 10) {
					d[i] = -5;
				} else {
					d[i] = d[i] % 5 * -1;
				}
			}
			i++;
		}
		System.out.println(new Dynamic().maxsequence2(d,0, d.length-1));
        System.out.println(new Dynamic().max3(111,22,3));
	}

	int maxsequence2(int a[], int l, int u) {
		if (l > u)
			return 0;
		if (l == u)
			return a[l];
		int m = (l + u) / 2;

		/* 求横跨左右的最大连续子序列左半部分 */
		int lmax = a[m], lsum = 0;
		for (int i = m; i >= l; i--) {
			lsum += a[i];
			if (lsum > lmax)
				lmax = lsum;
		}
		//System.out.println("左侧" + lmax);
		/* 求横跨左右的最大连续子序列右半部分 */
		int rmax = a[m + 1], rsum = 0;
		for (int i = m + 1; i <= u; i++) {
			rsum += a[i];
			if (rsum > rmax)
				rmax = rsum;
		}
		//System.out.println(rmax);
		return max3(lmax + rmax, maxsequence2(a, l, m), maxsequence2(a, m + 1, u)); // 返回三者最大值
	}

	/* 求三个数最大值 */
	int max3(int i, int j, int k) {
		if (i >= j && i >= k)
			return i;
		return max3(j, k, i);
	}
}
